//525.连续数组
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int findMaxLength(vector<int>& nums){
    //要求连续数组中0的个数和1的个数相同
    //将0装换成-1，这样连续数组和就为0，找和为0的数组最大长度

    //哈希表中key值表示下标i的前缀和，value值表示下标i
    unordered_map<int, int> hash;
    //初始时先将<0,-1>存放到哈希表中
    hash[0] = -1;

    int maxlen = 0, sum = 0;

    for (int i = 0; i < nums.size();i++){
        sum += nums[i] == 0 ? -1 : nums[i];

        //存在，更新长度
        if(hash.count(sum)){
            maxlen = max(maxlen,i - hash[sum]);
        }

        //不存在，插入前缀和
        if(!hash.count(sum)){
            hash[sum] = i;
        }
    }

    return maxlen;
}

int main(){
    vector<int> nums = {0,1,1,0,1,1,1,0};

    int maxlen = findMaxLength(nums);
    cout << maxlen;
    return 0;
}